package demo3;
import java.util.*;

class User {
    int id;
    String name;

    public User(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        User user = (User) o;
        return id == user.id;
    }

    @Override
    public int hashCode() {
        return Integer.hashCode(id);
    }
}

public class SocialNetworkFriendRecommendation {
    Map<User, Set<User>> userGraph = new HashMap<>();

    public void addFriendship(User user1, User user2) {
        userGraph.computeIfAbsent(user1, k -> new HashSet<>()).add(user2);
        userGraph.computeIfAbsent(user2, k -> new HashSet<>()).add(user1);
    }

    public Set<User> findCommonFriends(User user1, User user2) {
        Set<User> friends1 = userGraph.getOrDefault(user1, Collections.emptySet());
        Set<User> friends2 = userGraph.getOrDefault(user2, Collections.emptySet());
        Set<User> commonFriends = new HashSet<>(friends1);
        commonFriends.retainAll(friends2);
        return Collections.unmodifiableSet(commonFriends);
    }

    public Set<User> recommendFriends(User user) {
        Set<User> directFriends = userGraph.getOrDefault(user, Collections.emptySet());
        Set<User> possibleFriends = new HashSet<>();
        for (User friend : directFriends) {
            Set<User> friendsOfFriend = userGraph.getOrDefault(friend, Collections.emptySet());
            for (User potentialFriend : friendsOfFriend) {
                if (!directFriends.contains(potentialFriend) && !potentialFriend.equals(user)) {
                    possibleFriends.add(potentialFriend);
                }
            }
        }
        return Collections.unmodifiableSet(possibleFriends);
    }

    public static void main(String[] args) {
        SocialNetworkFriendRecommendation socialNetwork = new SocialNetworkFriendRecommendation();
        User user1 = new User(1, "Alice");
        User user2 = new User(2, "Bob");
        User user3 = new User(3, "Charlie");
        socialNetwork.addFriendship(user1, user2);
        socialNetwork.addFriendship(user2, user3);
        System.out.println("用户 1 和用户 2 的共同好友: " + socialNetwork.findCommonFriends(user1, user2));
        System.out.println("用户 1 可能认识的人: " + socialNetwork.recommendFriends(user1));
    }
}
